{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2e9380e2",
   "metadata": {},
   "source": [
    "# 插入排序算法\n",
    "\n",
    "## 1. 引言\n",
    "插入排序就像整理扑克牌，每次将一张新牌插入到已排序的手牌中。它的时间复杂度为：\n",
    "- 最坏情况：$O(n^2)$（逆序数组）\n",
    "- 最好情况：$O(n)$（已排序数组）\n",
    "适用于小规模数据或基本有序的数据。\n",
    "### 扑克牌类比：理解插入排序的本质\n",
    "假设你手中有5张已经按从小到大排序的扑克牌：♠3, ♥5, ♦7, ♣9, ♠J\n",
    "现在你摸到一张新牌：♦4\n",
    "排序过程模拟：\n",
    "1. 右手拿着新牌♦4，左手持已排序的牌\n",
    "2. 从右往左比较（从最大的♠J开始）：\n",
    "   - ♠J > ♦4 → 不需要移动\n",
    "   - ♣9 > ♦4 → 不需要移动\n",
    "   - ♦7 > ♦4 → 不需要移动\n",
    "   - ♥5 > ♦4 → 不需要移动\n",
    "   - ♠3 < ♦4 → 找到插入位置！\n",
    "3. 将♦4插入到♠3和♥5之间\n",
    "新序列：♠3, ♦4, ♥5, ♦7, ♣9, ♠J\n",
    "\n",
    "## 2. 算法步骤\n",
    "1. **外层循环**：从第二个元素开始遍历\n",
    "2. **内层循环**：将当前元素与前面已排序元素比较\n",
    "3. **插入操作**：找到合适位置后插\n",
    "\n",
    "\n",
    "**以下是插入排序的具体步骤：**\n",
    "1.  初始化\n",
    "2.  将数组的第一个元素视为已排序部分\n",
    "3.  从第二个元素开始遍历数组\n",
    "4.  取出当前元素\n",
    "5.  将当前元素（key）与已排序部分的元素从右到左进行比较\n",
    "6.  移动元素：\n",
    "    如果已排序部分的元素大于 key，则将该元素右移一位\n",
    "    重复此过程，直到找到 key 的正确位置\n",
    "7.  插入元素：将 key 插入到正确的位置\n",
    "8.  重复过程,继续处理数组中的下一个元素，直到所有元素都被插入到正确的位置\n",
    "\n",
    "## 3. 伪代码解析"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c5a5c07e",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSERTION-SORT(A, n):\n",
    "    for j = 2 to n:\n",
    "        key = A[j]\n",
    "        i = j - 1\n",
    "        while i > 0 and A[i] > key:\n",
    "            A[i+1] = A[i]\n",
    "            i = i - 1\n",
    "        A[i+1] = key"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b13c0f4d",
   "metadata": {},
   "source": [
    "#### 实例分析"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9a3206ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "初始数组: [88 95 88 19  4 34]\n",
      "排序过程:\n",
      "插入完成: [88 95 88 19  4 34]\n",
      "移动元素: [88 95 95 19  4 34] ← 当前位置1\n",
      "插入完成: [88 88 95 19  4 34]\n",
      "移动元素: [88 88 95 95  4 34] ← 当前位置2\n",
      "移动元素: [88 88 88 95  4 34] ← 当前位置1\n",
      "移动元素: [88 88 88 95  4 34] ← 当前位置0\n",
      "插入完成: [19 88 88 95  4 34]\n",
      "移动元素: [19 88 88 95 95 34] ← 当前位置3\n",
      "移动元素: [19 88 88 88 95 34] ← 当前位置2\n",
      "移动元素: [19 88 88 88 95 34] ← 当前位置1\n",
      "移动元素: [19 19 88 88 95 34] ← 当前位置0\n",
      "插入完成: [ 4 19 88 88 95 34]\n",
      "移动元素: [ 4 19 88 88 95 95] ← 当前位置4\n",
      "移动元素: [ 4 19 88 88 88 95] ← 当前位置3\n",
      "移动元素: [ 4 19 88 88 88 95] ← 当前位置2\n",
      "插入完成: [ 4 19 34 88 88 95]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([ 4, 19, 34, 88, 88, 95], dtype=int32)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def insertion_sort(arr):\n",
    "    for j in range(1, len(arr)):\n",
    "        key = arr[j]\n",
    "        i = j-1\n",
    "        while i >= 0 and arr[i] > key:\n",
    "            arr[i+1] = arr[i]\n",
    "            i -= 1\n",
    "            print(f\"移动元素: {arr} ← 当前位置{i+1}\")  # 可视化步骤\n",
    "        arr[i+1] = key\n",
    "        print(f\"插入完成: {arr}\")  # 可视化步骤\n",
    "    return arr\n",
    "\n",
    "# 测试示例\n",
    "import numpy as np\n",
    "unsorted = np.random.randint(1,100,6)#随机产生六个数\n",
    "print(\"初始数组:\", unsorted)\n",
    "print(\"排序过程:\")\n",
    "insertion_sort(unsorted.copy())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b00e0516",
   "metadata": {},
   "source": [
    "下面列举相关的例子"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b28808d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**初始状态:**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5 2 4 6 1 3]\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "\n",
       "**第1轮:** 处理元素 2（位置2）"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  移动 5 → 位置2\n",
      "插入完成: [2] 2 [5 4 6 1 3]\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "\n",
       "**第2轮:** 处理元素 4（位置3）"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  移动 5 → 位置3\n",
      "插入完成: [2 4] 4 [5 6 1 3]\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "\n",
       "**第3轮:** 处理元素 6（位置4）"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "插入完成: [2 4 5 6] 6 [1 3]\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "\n",
       "**第4轮:** 处理元素 1（位置5）"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  移动 6 → 位置5\n",
      "  移动 5 → 位置4\n",
      "  移动 4 → 位置3\n",
      "  移动 2 → 位置2\n",
      "插入完成: [1] 1 [2 4 5 6 3]\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "\n",
       "**第5轮:** 处理元素 3（位置6）"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  移动 6 → 位置6\n",
      "  移动 5 → 位置5\n",
      "  移动 4 → 位置4\n",
      "插入完成: [1 2 3] 3 [4 5 6]\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import display, Markdown\n",
    "import time\n",
    "\n",
    "def visualize_insertion(arr):\n",
    "    display(Markdown(\"**初始状态:**\"))\n",
    "    print(f\"[{' '.join(map(str, arr))}]\")\n",
    "    \n",
    "    for j in range(1, len(arr)):\n",
    "        key = arr[j]\n",
    "        i = j-1\n",
    "        display(Markdown(f\"\\n**第{j}轮:** 处理元素 {key}（位置{j+1}）\"))\n",
    "        \n",
    "        while i >= 0 and arr[i] > key:\n",
    "            arr[i+1] = arr[i]\n",
    "            print(f\"  移动 {arr[i]} → 位置{i+2}\")\n",
    "            i -= 1\n",
    "            time.sleep(1)\n",
    "        \n",
    "        arr[i+1] = key\n",
    "        print(f\"插入完成: [{' '.join(map(str, arr[:i+2]))}] {key} [{' '.join(map(str, arr[i+2:]))}]\")\n",
    "\n",
    "visualize_insertion([5, 2, 4, 6, 1, 3])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
